// @algorithm @lc id=1000265 lang=typescript
// @title 4ueAj6
// @test([3,4,1],2)  result: [3,2,4,1] ,expect: [3,4,1,2]
/**
 * Definition for node.
 * class Node {
 *     val: number
 *     next: Node | null
 *     constructor(val?: number, next?: Node) {
 *         this.val = (val===undefined ? 0 : val);
 *         this.next = (next===undefined ? null : next);
 *     }
 * }
 */

function insert(head: Node | null, insertVal: number): Node | null {
  let p = head;
  let maxNode = head;

  while (p) {
    // 找到最大的节点
    if (p.val > p.next.val) {
      maxNode = p;
    }
    // 找到合适的插入位置
    if (p.val <= insertVal && insertVal <= p.next.val) {
      break;
    }
    // 找了一圈，列表中间没有合适的插入位置，插入到最后
    if (p.next === head) {
      p = maxNode;
      break;
    }
    p = p.next;
  }

  if (p) {
    // 在p后面构建节点
    p.next = new Node(insertVal, p.next);
  } else {
    // head为null，构建节点
    head = new Node(insertVal);
    head.next = head;
  }

  return head;
}
